package com.dyz.leetcode._20_dynamicProgramming._494;

public class findTargetSumWays02 {
    //动态规划
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int i=0; i<n; i++){
            sum+=nums[i];
        }

        int diff = sum - target;
        if(diff<0 || diff%2!=0){return 0;}

        int neg  = diff/2;

        //动态规划
        int[][] dp = new int[n+1][neg+1];
        //base case
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];  //当前填满容量为j的包的方法数 = 之前填满容量为j的包的方法数 + 之前填满容量为j - num的包的方法数也就是当前数num的加入，可以把之前和为j - num的方法数加入进来。
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }

}
